#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/8/13 15:28
# @USER    : Shengji He
# @File    : MinimumWindowSubstring.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from collections import defaultdict


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        """
        Given a string S and a string T, find the minimum window in S which will contain all the characters
        in T in complexity O(n).

        Example:
            Input: S = "ADOBECODEBANC", T = "ABC"
            Output: "BANC"
        Note:
            - If there is no such window in S that covers all characters in T, return the empty string "".
            - If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

        :param s:
        :param t:
        :return:
        """
        need = defaultdict(int)
        for c in t:
            need[c] += 1
        needCnt = len(t)
        i = 0
        ans = (0, float('inf'))
        for j, c in enumerate(s):
            if need[c] > 0:
                needCnt -= 1
            need[c] -= 1
            if needCnt == 0:
                while True:
                    c = s[i]
                    if need[c] == 0:
                        break
                    need[c] += 1
                    i += 1
                if j - i < ans[1] - ans[0]:
                    ans = (i, j)
                need[s[i]] += 1
                needCnt += 1
                i += 1
        return '' if ans[1] > len(s) else s[ans[0]: ans[1] + 1]


if __name__ == '__main__':
    S = "ADOBECODEBANC"
    T = "ABC"
    s = Solution()
    print(s.minWindow(S, T))
    print('done')
